package lc.q101_150;

import lc.TreeNode;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Q105 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        return buildTree(Arrays.stream(preorder).boxed().collect(Collectors.toList()),
                Arrays.stream(inorder).boxed().collect(Collectors.toList())
                );
    }

    private TreeNode buildTree(List<Integer> preorder,
                               List<Integer> inorder) {
        // 改成list处理
        final Integer x = preorder.get(0);
        TreeNode treeNode = new TreeNode(x);
        // 左节点和右节点的处理
        // 只需要遍历一次就行，每次获取index
        int leftSize = 0;
        for (int i = 0; i < inorder.size(); i++) {
            if (inorder.get(i).equals(x)) {
                leftSize = i;
            }
        }
        if (leftSize != 0) {
            // 构建左树
            treeNode.left = buildTree(preorder.subList(1, leftSize+1), inorder.subList(0, leftSize));
        }
        if (leftSize != preorder.size() - 1) {
            treeNode.right = buildTree(preorder.subList(leftSize + 1, preorder.size()), inorder.subList(leftSize +1, preorder.size()));
        }
        return treeNode;
    }

    public static void main(String[] args) {
        final Q105 q105 = new Q105();
        final TreeNode node = q105.buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7});
        System.out.println(node);
    }
}
